package com.yun.algorithm.sort;

import java.util.ArrayList;
import java.util.Collections;

public class E03leetcode164 {

    public int maximumGap(int[] nums) {
        //1.
        if (nums.length < 2) {
            return 0;
        }
        //2.
        int max = nums[0];
        int min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
            if (nums[i] < min) {
                min = nums[i];
            }
        }
        if(max==min){
            return 0;
        }
        //2.1.准备桶
        /*
            计算桶个数
            (max-min)/range+1=nums.length+1
            range=(max-min)/(nums.length)
         */
        int range=Math.max((max-min)/nums.length,1);
        Pair[] buckets = new Pair[(max - min)/ range + 1];
        //2.2.放入数据
        for (int v : nums) {
            int idx = (v - min) / range;
            if(buckets[idx]==null){
                buckets[idx]=new Pair();
            }
            buckets[idx].add(v);
        }
        //3.
        int r = 0;
        int lastMax=buckets[0].max;
        for (int i = 1; i < buckets.length; i++) {
            Pair bucket = buckets[i];
            if(bucket!=null){
                r=Math.max(r,bucket.min-lastMax);
                lastMax=bucket.max;
            }
        }
        return r;
    }

    static class Pair{
        int max=0;
        int min=1000_000_000;

        void add(int v){
            max=Math.max(v,max);
            min=Math.min(v,min);
        }

        @Override
        public String toString() {
            return "[" + max + ", " + min + ']';
        }
    }

    public int maximumGap1(int[] nums) {
        //1.
        if (nums.length < 2) {
            return 0;
        }
        //2.
        int max = nums[0];
        int min = nums[0];
        for (int j : nums) {
            if (j > max) {
                max = j;
            }
            if (j < min) {
                min = j;
            }
        }
        if(max==min){
            return 0;
        }
        //2.1.准备桶
        /*
            计算桶个数
            (max-min)/range+1=nums.length
            range=(max-min)/(nums.length-1)
         */
        int range=(max-min)/(nums.length-1);
        ArrayList<Integer>[] buckets = new ArrayList[(max - min)/ range + 1];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<>();
        }
        //2.2.放入年龄数据
        for (int age : nums) {
            buckets[(age - min)/ range].add(age);
        }
        int k = 0;
        for (ArrayList<Integer> bucket : buckets) {
            //2.3.排序桶内排序
            Collections.sort(bucket);
            //2.4.把每个桶排序好的内容，依次放入原始数组
            for (Integer v : bucket) {
                nums[k++] = v;
            }
        }
        //3.
        int r = 0;
        for (int i = 1; i < nums.length; i++) {
            r = Math.max(r, nums[i] - nums[i - 1]);
        }
        return r;
    }

    public static void main(String[] args) {
        int[] nums=new int[]{1,1,1,1,1,5,5,5,5,5};
        System.out.println(new E03leetcode164().maximumGap(nums));
    }


    //基数排序
//        int max = nums[0];
//        for (int i = 1; i < nums.length; i++) {
//            max = Math.max(max, nums[i]);
//        }
//        ArrayList<Integer>[] buckets = new ArrayList[10];
//        for (int i = 0; i < 10; i++) {
//            buckets[i] = new ArrayList<>();
//        }
//        int m = 1;
//        while (m <= max) {
//            for (int i : nums) {
//                buckets[i / m % 10].add(i);
//            }
//            int k = 0;
//            for (ArrayList<Integer> bucket : buckets) {
//                for (Integer i : bucket) {
//                    nums[k++] = i;
//                }
//                bucket.clear();
//            }
//            m = m * 10;
//        }

    //3.寻找最大差值
}
